﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace PollServer
{
    public class QueueNode
    {
        public bool     IsEmpty;
        public int writting;
        public int reading;
        public object pObject;
        public QueueNode()
        {
            IsEmpty = true;
            writting = 0;
            reading = 0;
            pObject = null;
        }
    }
    ////无锁 生产/消费队列
    public class LockFreeQueue
    {
        //全局静态函数
        static private LockFreeQueue _queue;

        public static LockFreeQueue Queue
        {
            get
            {
                if (_queue == null)
                {
                    Interlocked.CompareExchange<LockFreeQueue>(ref _queue, new LockFreeQueue(10000), null);
                }
                return _queue;
            }
        }

        //私有参数
        private QueueNode[] m_queue;
        private long m_push;
        private long m_pop;
        private long m_nSize;
        private int m_nWriteAbleCount;   //允许写操作线程数量
        private int m_nReadAbleCount;    //允许读操作线程数量

        public LockFreeQueue(int size)
        {
            m_nSize = Convert.ToUInt32(size);
            m_nWriteAbleCount = size;
            m_nReadAbleCount = 0;
            m_queue = new QueueNode[m_nSize];
            m_push = 0;
            m_pop = 0;
            //
            init(size);
        }
        //初始化队列
        private void init(int size)
        {
            for (int i = 0; i < size; i++)
            {
                Interlocked.CompareExchange<QueueNode>(ref m_queue[i], new QueueNode(), null);
            }
        }

        //无锁push
        public bool push(object _node)
        {
            if (0 >= m_nWriteAbleCount) return false;//队列已满
            //最多允许m_nWriteAbleCount多个push线程操作队列，确保之后遍历的操作一定能够找到空位插入
            if (0 > Interlocked.Decrement(ref m_nWriteAbleCount)) //原子操作减一
            {
                Interlocked.Increment(ref m_nWriteAbleCount); //原子操作加一
                return false;
            }

            long pushPos = m_push; //取push的位置
            Interlocked.Increment(ref m_push); //加一

            for (int i = 0; i < m_nSize; i++, pushPos++ )
            {
                pushPos = pushPos % m_nSize;
                //数据是否被写
                if (!m_queue[pushPos].IsEmpty) continue;
                //保证数据只写一次
                if (Interlocked.CompareExchange(ref m_queue[pushPos].writting, 1, 0) > 0) continue;
                
                //成功找到
                break;
            }
            m_queue[pushPos].pObject = _node;
            m_queue[pushPos].IsEmpty = false;
            m_queue[pushPos].reading = 0;
            //增加可读数量
            Interlocked.Increment(ref m_nReadAbleCount); //原子操作加一
            
            return true;
        }

        //无锁Pop
        public object pop()
        {
            if (0 >= m_nReadAbleCount) return null;//空队列
            //最多允许m_nReadAbleCount多个Pop线程操作队列，确保之后遍历的操作一定能够找到数据取出
            if (0 > Interlocked.Decrement(ref m_nReadAbleCount)) //原子操作减一
            {
                Interlocked.Increment(ref m_nReadAbleCount);  //原子操作加一
                return null;
            }

            long popPos = m_pop;
            Interlocked.Increment(ref m_pop);

            for (int i = 0; i < m_nSize; i++, popPos++)
            {
                popPos = popPos % m_nSize;
                //检查数据是否被写
                if (m_queue[popPos].IsEmpty) continue;
                //保证数据只读一次
                if (Interlocked.CompareExchange(ref m_queue[popPos].reading, 1, 0) > 0) continue;
                //
                break;
            }

            object pObject = m_queue[popPos].pObject;
            m_queue[popPos].pObject = null;
            m_queue[popPos].IsEmpty = true;
            m_queue[popPos].writting = 0;
            //增加可写数量
            Interlocked.Increment(ref m_nWriteAbleCount);

            return pObject;
        }

    }
}
